package Recursion;

import java.util.*;

public class Solution2 {
    /*n皇后问题*/
    private int res;
    //判断皇后是否符合条件
    private boolean isValid(int[] pos, int row, int col){
        //遍历所有已经记录的行
        for(int i = 0; i < row; i++){
            //不能同行同列同一斜线
            if(row == i || col == pos[i] || Math.abs(row - i) == Math.abs(col - pos[i]))
                return false;
        }
        return true;
    }

    //递归查找皇后种类
    private void recursion1(int n, int row, int[] pos){
        //完成全部行都选择了位置
        if(row == n){
            res++;
            return;
        }
        //遍历所有列
        for(int i = 0; i < n; i++){
            //检查该位置是否符合条件
            if(isValid(pos, row, i)){
                //加入位置
                pos[row] = i;
                //递归继续查找
                recursion1(n, row + 1, pos);
            }
        }
    }
    public int Nqueen (int n) {
        res = 0;
        //下标为行号，元素为列号，记录皇后位置
        int[] pos = new int[n];
        Arrays.fill(pos, 0);
        //递归
        recursion1(n, 0, pos);
        return res;
    }
    /*括号生成：做过的那道题是括号匹配！*/
    void recursion(int left,int right,String temp,ArrayList<String> res,int n){
        if (left == n && right == n){
            res.add(temp);
            return;
        }
        if (left < n){
            recursion(left+1,right,temp+"(",res,n);
        }
        if (right < n && left > right){
            recursion(left,right+1,temp+")",res,n);
        }
    }
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        //记录结果
        ArrayList<String > res = new ArrayList<>();
        //记录每次组装的字符串
        String temp =new String();
        //递归
        recursion(0,0,temp,res,n);
        return res;
    }


}
